﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStruct
{
    public class DoubleNode
    {
        public int Data;
        public DoubleNode Pre;
        public DoubleNode Next;
        public DoubleNode(int data, DoubleNode pre = null, DoubleNode next = null)
        {
            Data = data;
            Pre = pre;
            Next = next;
        }
    }

    public class DoubleLinkedList
    {
        public DoubleNode first;//头节点指针
        public DoubleNode last;//尾指针
        int _length;//链表长度

        public DoubleLinkedList()
        {
            for (int i = 0; i <= 5; i++)
            {
                InsertInLast(i);
            }
        }

        /// <summary>
        /// 前插法--插入元素
        /// </summary>
        /// <param name="data"></param>
        public void InsertInHead(int data)
        {
            DoubleNode newNode = new DoubleNode(data);
            if (first == null)//首次插入节点
            {
                first = newNode;
                last = newNode;
                _length++;
                return;
            }

            newNode.Next = first; //步骤1 新节点后驱指针指向头节点First
            first.Pre = newNode;  //步骤2 头节点First的前驱指针指向新节点
            first = newNode;      //步骤3 头节点指针First指向新节点
            _length++;
        }

        /// <summary>
        /// 尾插法插入元素
        /// </summary>
        /// <param name="data"></param>
        public void InsertInLast(int data)
        {
            DoubleNode newNode = new DoubleNode(data);
            if (first == null)
            {
                first = newNode;
                last = newNode;
                _length++;
                return;
            }
            last.Next = newNode;//步骤1、尾指针后驱指针指向新节点
            newNode.Pre = last; //步骤2、新节点前驱指针指向尾节点
            last = newNode;     //步骤3、尾节点Last指向新节点
            _length++;
        }

        /// <summary>
        /// 删除元素
        /// </summary>
        /// <param name="data"></param>
public void DeleteByValue(int data)
{
    if (first == null)
    {
        return;
    }

    DoubleNode currentNode = first;
    DoubleNode pre = null;

    while (currentNode != null && currentNode.Data != data)
    {
        pre = currentNode;
        currentNode = currentNode.Next;
    }

    //没有找到要删除的节点
    if (currentNode == null)
    {
        return;
    }

    //删除头节点
    if (currentNode == first)
    {
        if (_length == 1)
        {
            first = null;
            last = null;
            _length--;
            return;
        }

        first = first.Next;
        first.Pre = null;
        _length--;
        return;
    }

    //删除尾节点
    if (currentNode == last)
    {
        last = last.Pre;
        last.Next = null;
        _length--;
        return;
    }
    //删除中间节点
    pre.Next = currentNode.Next;
    currentNode.Next.Pre = pre;
    _length--;
}

        /// <summary>
        /// 删除:按索引删除 删除单链表中第index个节点
        /// </summary>
        /// <param name="index"></param>
        public void DeleteByIndex(int index)
        {
            //删除第一个节点
            if (index == 1)
            {
                if (_length == 1)//只有一个节点
                {
                    first = null;
                    last = null;
                    _length--;
                    return;
                }
                //有多个节点
                first = first.Next;
                first.Pre = null;
                _length--;
                return;
            }
            //删除最后一个节点
            if (index == _length)
            {
                last = last.Pre;
                last.Next = null;
                _length--;
                return;
            }
            //删除中间节点
            DoubleNode currentNode = first;
            DoubleNode preNode = null;
            int i = 1;
            //找到第i个节点
            while (i != index)
            {
                preNode = currentNode;
                currentNode = currentNode.Next;
                i++;
            }

            preNode.Next = currentNode.Next;
            currentNode.Next.Pre = preNode;
            _length--;
        }

        /// <summary>
        /// 查找:按索引查找 查找单链表中第index个节点
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public DoubleNode GetByIndex(int index)
        {
            var currentNode = first;
            int i = 1;
            while (i != index)
            {
                currentNode = currentNode.Next;
                i++;
            }
            return currentNode;
        }

        /// <summary>
        /// 查找:按值查找
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public DoubleNode GetByData(int data)
        {
            DoubleNode currentNode = first;
            while (currentNode != null && currentNode.Data != data)
            {
                currentNode = currentNode.Next;
            }
            return currentNode;
        }

        /// <summary>
        /// 插入:在第index个位置插入数据data
        /// </summary>
        /// <param name="index"></param>
        /// <param name="data"></param>
        public void Insert(int index, int data)
        {
            //头部插入
            if (index == 1)
            {
                InsertInHead(data);
                return;
            }
            //尾部插入
            if (index > _length)
            {
                InsertInLast(data);
                return;
            }
            //中间插入
            int i = 1;
            DoubleNode currentNode = first;
            DoubleNode preNode = null;
            while (i != index)
            {
                preNode = currentNode;
                currentNode = currentNode.Next;
                i++;
            }

            DoubleNode newNode = new DoubleNode(data);
            preNode.Next = newNode;             //步骤1、指定位置的前一个节点的后驱动指针指向新节点
            newNode.Pre = preNode;              //步骤2、新节点的前驱指针指向指定位置的前一个节点:
            newNode.Next = currentNode;         //步骤3、新节点的后去指针指向指定位置的节点
            currentNode.Pre = newNode;          //步骤4、指定位置节点的前驱指针指向新节点
            _length++;
        }

        ///// <summary>
        ///// 链表反转
        ///// </summary>
        //public void Reverse()
        //{
        //    var tempFirst = First;
        //    var tempLast = Last;
        //    Node current = First;
        //    Node pre = null;
        //    Node prepre = null;
        //    while (current != null)
        //    {
        //        prepre = pre;
        //        pre = current;
        //        current = current.Next;
        //        pre.Next = prepre;
        //    }

        //    First = tempLast;
        //    Last = tempFirst;
        //}

        /// <summary>
        /// 链表是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return first == null || last == null;
        }

        /// <summary>
        /// 清空链表
        /// </summary>
        /// <returns></returns>
        public void Clear()
        {
            first = null;
            last = null;
        }

        /// <summary>
        /// 获取链表长度
        /// </summary>
        /// <returns></returns>
        public int GetLength()
        {
            if (first == null)
            {
                return 0;
            }
            int count = 0;
            DoubleNode current = first;
            while (current != null)
            {
                count++;
                current = current.Next;
            }
            return count;
        }

        /// <summary>
        /// 输出环形链表
        /// </summary>
        public void Print()
        {
            if (first == null)
            {
                return;
            }

            DoubleNode current = first;
            while (current != null)
            {
                Console.Write($"{current.Data} ");
                current = current.Next;
            }

            Console.WriteLine($"头节点:{first.Data},尾节点:{last.Data},链表长度:{GetLength()}——{_length}");
        }
    }
}
